import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

//暴力解法
class Solution1 {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][n];

        //k j i
        int sum = 0;
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<i; j++) {
                for(int k = 0;k<j; k++) {
                    if((long)nums[i] - nums[j] == (long)nums[j] - nums[k]) {
                        dp[j][i] = dp[k][j] + dp[j][i]+1;
                    }
                }
                sum += dp[j][i];
            }
        }
        return sum;
    }
}

class Solution2 {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n][n];
        Map<Long, List<Integer>> map = new HashMap<>();
        for(int i = 0; i<n; i++) {
            long tmp = (long) nums[i];
            if(!map.containsKey(tmp)) {
                List<Integer> list = new ArrayList<>();
                list.add(i);
                map.put(tmp, list);
            }else {
                map.get(tmp).add(i);
            }
        }
        //k j i
        int sum = 0;
        for(int i = 0; i<n; i++) {
            for(int j = 0; j<i; j++) {
                if(map.containsKey((2*(long)nums[j] - (long)nums[i]))) {
                    List<Integer> list = map.get((2*(long)nums[j] - (long)nums[i]));
                    for(int k : list) {
                        if(k < j) {
                            dp[j][i] = dp[k][j] + dp[j][i]+1;
                        }
                    }
                    sum += dp[j][i];
                }
            }
        }
        return sum;
    }
}

class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution3 {
    public ListNode reverseList(ListNode head) {
        ListNode newHead = new ListNode();
        ListNode cur = head;
        while(cur!=null) {
            ListNode next = cur.next;
            cur.next = newHead.next;
            newHead.next = cur;
            cur = next;
        }
        return newHead.next;
    }
}

class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while(fast!=null && fast.next!=null) {
            slow = slow.next;
            fast = fast.next.next;
            if(fast == slow) {
                break;
            }
        }

        //链表无环
        if(fast==null||fast.next==null) return null;

        while(head!=slow) {
            head = head.next;
            slow = slow.next;
        }
        return head;
    }
}



public class Test {

}
